#include "hw5.h"

/*****核心功能函数（递归）*****/
bool search(int k, btree root)
{
    if (root == nullptr)
    {
        return false;
    }
    else if (k == root->data)
    {
        return true;
    }
    else
    {
        if (search(k, root->lc) == true || search(k, root->rc) == true)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}
/*****核心功能函数*****/

/*****主函数*****/
int main()
{
    printf("递归\n\n\n\n");

    t0 = NULL;
    t1 = (btree)malloc(sizeof(btnode));
    t2 = (btree)malloc(sizeof(btnode));
    t3 = (btree)malloc(sizeof(btnode));
    t4 = (btree)malloc(sizeof(btnode));
    t5 = (btree)malloc(sizeof(btnode));
    t6 = (btree)malloc(sizeof(btnode));
    t7 = (btree)malloc(sizeof(btnode));
    t8 = (btree)malloc(sizeof(btnode));
    t9 = (btree)malloc(sizeof(btnode));

    /***第1棵非BST的二叉树***/
    printf("/*****第1棵非BST的二叉树*****/\n");
    t_init();
    t1->lc = t2;
    t1->rc = t3;
    t2->lc = t4;
    t2->rc = t5;
    t3->lc = t6;
    t3->rc = t7;
    print_t(t1);
    if (search(5, t1) == true)
    {
        printf("5 is in this binary tree.\n");
    }
    else
    {
        printf("5 is in not this binary tree.\n");
    }
    printf("/*****第1棵非BST的二叉树*****/\n\n\n\n");
    /***第1棵非BST的二叉树***/

    /***第2棵非BST的二叉树***/
    printf("/*****第2棵非BST的二叉树*****/\n");
    t_init();
    t5->lc = t3;
    t3->lc = t2;
    t5->rc = t7;
    t7->lc = t6;
    t7->rc = t9;
    t9->lc = t8;
    print_t(t5);
    if (search(15, t5) == true)
    {
        printf("15 is in this binary tree.\n");
    }
    else
    {
        printf("15 is not in this binary tree.\n");
    }
    printf("/*****第2棵非BST的二叉树*****/\n\n\n\n");
    /***第2棵非BST的二叉树***/

    /***第3棵非BST的二叉树***/
    printf("/*****第3棵非BST的二叉树*****/\n");
    t_init();
    t5->lc = t3;
    t3->lc = t2;
    t3->rc = t4;
    t4->lc = t1;
    t5->rc = t7;
    t7->lc = t6;
    t7->rc = t9;
    t9->lc = t8;
    print_t(t5);
    if (search(8, t5) == true)
    {
        printf("8 is in this binary tree.\n");
    }
    else
    {
        printf("8 is not in this binary tree.\n");
    }
    printf("/*****第3棵非BST的二叉树*****/\n\n\n\n");
    /***第3棵非BST的二叉树***/

    /***第4棵非BST的二叉树***/
    printf("/*****第4棵非BST的二叉树*****/\n");
    t_init();
    t5->lc = t3;
    t3->lc = t2;
    t3->rc = t4;
    t2->rc = t1;
    t5->rc = t7;
    t7->lc = t6;
    t7->rc = t9;
    t9->lc = t8;
    print_t(t5);
    if (search(0, t5) == true)
    {
        printf("0 is in this binary tree.\n");
    }
    else
    {
        printf("0 is not in this binary tree.\n");
    }
    printf("/*****第4棵非BST的二叉树*****/\n\n\n\n");
    /***第4棵非BST的二叉树***/

    system("pause");
}